import java.util.*;

/**
 * @Author 12629
 * @Description：
 */
public class Test {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.display3(mySingleList.head);
        System.out.println();
        mySingleList.display4();

    }
    public static void main66(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("hello");
        linkedList.add("abc");
        linkedList.add("def");
        linkedList.add("ok");
        System.out.println(linkedList);
        System.out.println("===========");
        for(String x : linkedList) {
            System.out.println(x);
        }
        System.out.println("===========");
        ListIterator<String> it = linkedList.listIterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        System.out.println("=====反向======");
        ListIterator<String> it2 = linkedList.listIterator(linkedList.size());
        while (it2.hasPrevious()) {
            System.out.println(it2.previous());
        }


        ArrayList<String> list = new ArrayList<>();

        LinkedList<String> linkedList2 = new LinkedList<String>(list);


    }

    public static void main55(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(3);
        myLinkedList.display();


        LinkedList<Integer> list = new LinkedList<>();

        System.out.println("=================");

        myLinkedList.removeAllKey(3);
        myLinkedList.display();



    }
    public static MySingleList.ListNode mergeTwoLists
            (MySingleList.ListNode head1, MySingleList.ListNode head2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(0);
        MySingleList.ListNode tmp = newHead;

        while (head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if(head1 != null) {
            tmp.next = head1;
        }
        if(head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;
    }

    public static MySingleList.ListNode getIntersectionNode
            (MySingleList.ListNode headA, MySingleList.ListNode headB) {

        if(headA == null && headB == null) {
            return null;
        }

        //1、分别求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        //2. 要指回来，因为求完长度后pl和ps为空
        pl = headA;
        ps = headB;
        int len = lenA - lenB;//大小
        //3、根据Length的值 修改指向
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB-lenA;
        }
        //1. len一定是一个正数  2.pl指向的链表一定是最长的  ps 指向的链表一定是最短的

        while (len != 0) {//先让长的链表中的“指针”先走个“相差的长度”
            pl = pl.next;
            len--;
        }
        while (pl != ps) {//然后再一步一步走
            pl = pl.next;
            ps = ps.next;
        }
        //pl == ps——当执行完上面的while语句时，pl一定等于ps
       /* if(pl == null) {    如果pl为空，因为此时pl等于ps，所以ps也为空。返回null
            return null;
        }
        return pl;*/
        return pl;  //可以再简化一下为这个
    }

    public static void createCut(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        headB.next.next = headA.next.next;
    }

    public static void main5(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(11);
        mySingleList.addLast(21);
        mySingleList.addLast(31);
        mySingleList.addLast(41);
        mySingleList.display();
        mySingleList.createLoop();

        boolean flg = mySingleList.hasCycle();
        System.out.println(flg);

        MySingleList.ListNode ret = mySingleList.detectCycle();
        System.out.println(ret.val);

    }


    public static void main4(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(11);
        mySingleList.addLast(21);
        mySingleList.addLast(31);
        mySingleList.addLast(41);
        mySingleList.display();


        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(8);
        mySingleList2.addLast(15);
        mySingleList2.addLast(25);
        mySingleList2.addLast(30);
        mySingleList2.display();

        System.out.println("===============");
        /*MySingleList.ListNode ret =
                mergeTwoLists(mySingleList.head,mySingleList2.head);
        mySingleList2.display(ret);*/

        createCut(mySingleList.head,mySingleList2.head);

        MySingleList.ListNode ret = getIntersectionNode(mySingleList.head,mySingleList2.head);
        System.out.println(ret.val);
    }



    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        System.out.println("====测试插入===");
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.display();
        System.out.println("=========");
        /*MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.display(ret.next);*/
        MySingleList.ListNode ret = mySingleList.findKthToTail(5);
        System.out.println(ret.val);
    }
    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createLink();
        mySingleList.display();
        System.out.println("=======");
        System.out.println(mySingleList.contains(90));
        System.out.println(mySingleList.size());
        System.out.println("====测试插入===");
        mySingleList.addLast(1);
        mySingleList.addLast(1);
        mySingleList.addLast(1);
        mySingleList.addLast(1);
        try {
            mySingleList.addIndex(0,1);
        }catch (ListIndexOutOfException e) {
            e.printStackTrace();
        }
        mySingleList.display();
        System.out.println("=============");
        mySingleList.removeAllKey(1);
        mySingleList.display();
    }


    public void merge(int A[], int m, int B[], int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        // 两个数组当中  都有数据
        while (i >= 0 && j >= 0) {
            if(A[i] <= B[j]) {
                A[k] = B[j];
                j--;
                k--;
            }else {
                A[k] = A[i];
                k--;
                i--;
            }
        }
        //有可能A走完了 但是B里面仍然有数据
        while (j >= 0) {
            A[k] = B[j];
            j--;
            k--;
        }
    }

    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextLine()) {
            String str = scan.nextLine();
            String ret = func(str);
            System.out.println(ret);
        }
    }
    private static String func(String str) {
        boolean[] flg = new boolean[127];//false
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length();i++) {
            char ch = str.charAt(i);
            if(flg[ch] == false) {
                sb.append(ch);
                flg[ch] = true;
            }
        }
        return sb.toString();
    }
}
